package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type MyNode struct {
	n   *TreeNode
	sum int
}

func hasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	stack := []*MyNode{
		{n: root, sum: root.Val},
	}
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if top.n.Left == nil && top.n.Right == nil && top.sum == sum {
			return true
		}
		if top.n.Left != nil {
			stack = append(stack, &MyNode{n: top.n.Left, sum: top.sum + top.n.Left.Val})
		}
		if top.n.Right != nil {
			stack = append(stack, &MyNode{n: top.n.Right, sum: top.sum + top.n.Right.Val})
		}
	}
	return false
}

func main() {
	n0 := &TreeNode{Val: 5}
	n1 := &TreeNode{Val: 4}
	n2 := &TreeNode{Val: 8}
	n3 := &TreeNode{Val: 11}
	n4 := &TreeNode{Val: 2}
	n0.Left = n1
	n0.Right = n2
	n2.Left = n3
	n3.Left = n4
	result := hasPathSum(n0, 9)
	println(result)
}
